package listbyorder.access101_200.test115;

import java.util.HashMap;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/8 8:48
 */
public class Solution2 {

    // 方法二： 简单优化，用HashMap做一下缓存
    public int numDistinct(String s, String t) {
        if (s.length() < t.length()) return 0;
        HashMap<String, Integer> memo = new HashMap<>();
        return getAns(s, 0, t, 0, memo);
    }

    private int getAns(String s, int c1, String t, int c2, HashMap<String, Integer> memo) {
        // 如果t是空串，一种选择方法
        if (c2 == t.length()) return 1;
        // s的长度小于t的长度返回0
        if (s.length() - c1 < t.length() - c2) return 0;

        String cur = c1 + "@" + c2;
        if (memo.containsKey(cur)) return memo.get(cur);
        int res = 0;
        if (s.charAt(c1) == t.charAt(c2)) {
            res = getAns(s, c1 + 1, t, c2 + 1, memo) + getAns(s, c1 + 1, t, c2, memo);
        } else {
            res = getAns(s, c1 + 1, t, c2, memo);
        }
        memo.put(cur, res);
        return res;
    }


}
